public class Code2 {
    // 地下城游戏

    // 这个路径问题有别于其他，顺序是从下向上，从右到左

    public int calculateMinimumHP(int[][] dungeon) {
        // 1、创建 dp 表
        // 2、初始化操作
        // 3、填表
        // 4、确定返回值

        //这里 dp 表的创建规模是和矩阵一样的 但是在最后需要多加上一行，最右侧多添加上一列
        int m = dungeon.length;
        int n = dungeon[0].length;

        int[][] dp = new int[m+1][n+1];
        // 因为这里需要最后向上相加得出值，这里需要将最后一行和最右侧一列 设置为正无穷大
        for(int j = 0; j <= n; j++){
            dp[m][j] = Integer.MAX_VALUE;
        }
        for(int i = 0; i <= m; i++){
            dp[i][n] = Integer.MAX_VALUE;
        }
        dp[m][n - 1] = dp[m - 1][n] = 1;

        // 需要注意的是这里的填表顺序是从右向左从下向上
        for(int i = m - 1; i >= 0; i--){
            for(int j = n - 1; j >= 0; j--){
                dp[i][j] = Math.min(dp[i][j + 1],dp[i + 1][j]) - dungeon[i][j];
                dp[i][j] = Math.max(dp[i][j], 1);
            }
        }
        return dp[0][0];
    }
}
